'''
AVL树:
    AVL树是一颗自平衡的二叉树
    AVL树具有以下性质:
        根的左右子树的高度之差的绝对值不能超过1
        根的左右子树都是平衡二叉树
    AVL树--插入:
        插入一个节点可能会破坏AVL树的平衡,可以通过旋转操作来修正
        插入一个节点后, 只有从插入节点到根节点的路径上的结点的平衡可能被改变.我们需要找出第一个破坏了平衡条件的结点,称之为K,.K的两颗子树的高度差2
        不平衡的出现可能有4种情况
'''
class AVLNode:
    # 节点构造函数
    def __init__(self, data):
        self.data = data  # 节点存储的数据值
        self.lchild = None  # 左子节点指针（初始为空）
        self.rchild = None  # 右子节点指针（初始为空）
        self.parent = None  # 父节点指针（初始为空）
        self.bf = 0  # balance factor

class AVLTree:
    def __init__(self, li=None):
        self.root = None  # 树的根节点（初始为空）
        # 如果提供了初始列表，按顺序插入所有元素
        if li:
            for val in li:
                self.insert_no_rec(val)

    def rotate_left(self,p,c):
        s2 = c.lchild
        p.rchild = s2
        if s2:
            s2.parient = p

        c.lchild = p
        p.parient = c

        p.bf = 0
        c.bf = 0

    def insert_no_rec(self, val):
        p = self.root  # 从根节点开始遍历

        # 情况1：空树 → 直接创建根节点
        if not p:  # 空树检查
            self.root = BiTreeNode(val)  # 创建根节点
            return  # 插入完成

        # 情况2：非空树 → 寻找插入位置
        while True:
            # 向左子树查找插入位置
            if val < p.data:
                if p.lchild:  # 左子节点存在
                    p = p.lchild  # 向左移动
                else:  # 找到插入位置
                    p.lchild = BiTreeNode(val)  # 创建左子节点
                    p.lchild.parent = p  # 设置父指针
                    return  # 插入完成

            # 向右子树查找插入位置
            elif val > p.data:
                if p.rchild:  # 右子节点存在
                    p = p.rchild  # 向右移动
                else:  # 找到插入位置
                    p.rchild = BiTreeNode(val)  # 创建右子节点
                    p.rchild.parent = p  # 设置父指针
                    return  # 插入完成

            # 值已存在 → 不插入（BST不允许重复）
            else:
                return  # 不做操作